package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 括号生成 {
	List<String>res=new ArrayList<>();
	StringBuilder path=new StringBuilder();
	public List<String> method1(int n) {
		recursion(n,n);
		return res;
	}
	// 自己写出 花费30min
	// 摸索出了括号的规律，只要左括号多于右括号，那么就可以加上左括号或者右括号
	// 否则只能加左括号
	// 然后递归头是leftNum=0时，这时候需要将剩下的右括号加入到path中，但是path出去的时候要和进来的一样
	// 为了这一目的 直接用一个temp来构造结果保存，就不去动path了
	// 力扣的写法会更加简单 练习的时候去看看·
	public void recursion(int leftNum,int rightNum){
		if(leftNum==0){
			StringBuilder temp=new StringBuilder(path);
			while(rightNum!=0){
				temp.append(")");
				rightNum--;
			}
			res.add(temp.toString());
			return;
		}
		if(leftNum<rightNum){
			for (int i = 0; i < 2; i++) {
				if(i==0){
					path.append("(");
					recursion(leftNum-1,rightNum);
				}else{
					path.append(")");
					recursion(leftNum,rightNum-1);
				}
				path.deleteCharAt(path.length()-1);
			}
		}else{
			path.append("(");
			recursion(leftNum-1,rightNum);
			path.deleteCharAt(path.length()-1);
		}
	}

	public List<String> practice(int n) {
		recursionPractice(n,n);
		return res;
	}

	public void recursionPractice(int left,int right){
		if(right<left||left<0){
			return;
		}
		if(left==0&&right==0){
			res.add(path.toString());
			return;
		}
		char[]temp={'(',')'};
		//这边两种情况可以不用循环，直接写就行
		for (char c : temp) {
			path.append(c);
			if(c=='('){
				recursionPractice(left-1,right);
			}else{
				recursionPractice(left,right-1);
			}
			path.deleteCharAt(path.length()-1);
		}
	}
}
